/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
    ListNode *get(ListNode *&p, int n){
        if (p==NULL) return NULL;
        ListNode *head=p;
        for (int i=1;i<n && p!=NULL;i++, p=p->next);
        ListNode *tmp=p->next;
        p->next=NULL;
        p=tmp;
        return head;
    }
    void reverse(ListNode *&p) {
        ListNode guard(-1);
        while (p!=NULL) {
            ListNode *data=p;
            p=p->next;
            data->next=guard.next;
            guard.next=data;
        }
        p=guard.next;
    }
    void add(ListNode *&head, ListNode *&tail, ListNode *&p) {
        if (p==NULL) return;
        if (tail==NULL)
            head=tail=p;
        else {
            tail->next=p;
            tail=tail->next;
        }
        p=p->next;
    }
public:
    void reorderList(ListNode *head) {
        if (head==NULL) return;
        int n=0;
        for (ListNode *x=head;x!=NULL;x=x->next, ++n);
        ListNode *p1=get(head, (n+1)/2), *p2=head;
        reverse(p2);
        ListNode *tail;
        head=tail=NULL;
        while (p1!=NULL || p2!=NULL) {
            add(head, tail, p1);
            add(head, tail, p2);
        }
    }
};
